package graphPath;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

import org.jgrapht.WeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;

public class DijkstraPath {
	public Map<String, Double> distance;
	public Map<String, String> parent;

	Set<Set<String>> filterSet;

	public DijkstraPath() {

		this.distance = new HashMap<String, Double>();
		this.parent = new HashMap<String, String>();
		this.filterSet = new HashSet<Set<String>>();
	}

	// initialization
	public void initialize(WeightedGraph<String, DefaultWeightedEdge> graph,
			String source) {

		for (String vertex : graph.vertexSet()) {
			distance.put(vertex, Double.POSITIVE_INFINITY);
			parent.put(vertex, null);
		}

		distance.put(source, 0d);
	}

	// Relaxation: compare the weight
	public void relax(String u, String v,
			WeightedGraph<String, DefaultWeightedEdge> graph) {
		if (distance.get(v) > distance.get(u)
				+ graph.getEdgeWeight(graph.getEdge(u, v))) {

			double dis = distance.get(u)
					+ graph.getEdgeWeight(graph.getEdge(u, v));
			distance.put(v, dis);
			parent.put(v, u);

		}

	}

	// find path
	public Set<Map.Entry<String, Double>> dijkstra(
			WeightedGraph<String, DefaultWeightedEdge> graph, String source) {
		initialize(graph, source);

		Set<Map.Entry<String, Double>> vertices = new HashSet<Map.Entry<String, Double>>();

		Map<Map.Entry<String, String>, Double> edges = new HashMap<Map.Entry<String, String>, Double>();

		List<Map.Entry<String, Double>> list = new ArrayList<Map.Entry<String, Double>>(
				distance.entrySet());
		Queue<Map.Entry<String, Double>> queue = new PriorityQueue<Map.Entry<String, Double>>(
				list.size(), new Comparator<Map.Entry<String, Double>>() {

					public int compare(Map.Entry<String, Double> o1,
							Map.Entry<String, Double> o2) {
						
						return o1.getValue().compareTo(o2.getValue());
					}
				});

		queue.addAll(list);

		while (queue.size() > 0) {

			list.clear();
			list.addAll(queue);
			queue.clear();
			queue.addAll(list);
			Map.Entry<String, Double> u = queue.poll();

			vertices.add(u);

			Map<String, String> walkthrough = new HashMap<String, String>();
			walkthrough.put(source, u.getKey());
			List<Map.Entry<String, String>> walkthroughEntry = new ArrayList<Map.Entry<String, String>>(
					walkthrough.entrySet());

			edges.put(walkthroughEntry.get(0), u.getValue());

			for (Integer element : getNeighborSet(graph,
					Integer.parseInt(u.getKey()))) {
				relax(u.getKey(), String.valueOf(element), graph);

			}

		}
		// System.out.println(distance);
		// System.out.println(vertices);
		DecimalFormat f = new DecimalFormat("######.00");
		DecimalFormat f2 = new DecimalFormat("0.00");

		for (Map.Entry<String, String> key : edges.keySet()) {

			if (edges.get(key) == Double.POSITIVE_INFINITY) {

				Set<String> pair = new HashSet<String>(2);
				pair.add(key.getKey());
				pair.add(key.getValue());
				if (!filterSet.contains(pair)) {
					filterSet.add(pair);
					System.out.println(key.getKey() + "-->" + key.getValue()
							+ " Disconnected graph (no path).");
				}
			} else {

				Set<String> pair = new HashSet<String>(2);
				pair.add(key.getKey());
				pair.add(key.getValue());
				if (!filterSet.contains(pair)) {
					filterSet.add(pair);
					System.out.print(key.getKey() + "-->" + key.getValue()
							+ " Path Weight :" + f.format(edges.get(key))
							+ "  ");
					String parentNode = parent.get(key.getValue());
					String currentNode = key.getValue();

					while (parentNode != null
							&& !parentNode.equals(currentNode)) {
						System.out
								.print("["
										+ parentNode
										+ "-->"
										+ currentNode
										+ ", "
										+ f.format((distance.get(currentNode) - distance
												.get(parentNode))) + "]");
						currentNode = parentNode;
						parentNode = parent.get(parentNode);

					}

					if (parentNode != null)
						System.out.print(parentNode + "-->" + key.getKey());
					System.out.println();
				}
			}

			// System.out.println(filterSet);

		}
		// System.out.println(edges);
		// System.out.println(parent);
		return vertices;
	}

	// find the neighborSet of specific vertex
	public List<Integer> getNeighborSet(
			WeightedGraph<String, DefaultWeightedEdge> graph, int v) {
		List<String> neighbor = new ArrayList<String>();
		List<Integer> result = new ArrayList<Integer>();

		for (DefaultWeightedEdge element : graph.edgesOf(String.valueOf(v))) {
			if (graph.getEdgeSource(element).equals(String.valueOf(v))) {
				neighbor.add(graph.getEdgeTarget(element));

			} else {
				neighbor.add(graph.getEdgeSource(element));
			}
		}

		for (String element : neighbor) {
			result.add(Integer.parseInt(element));
		}

		return result;

	}

}
